1. Field of the Invention
The present invention relates to a one-way data conversion apparatus and a device authentication system in which it is used. In particular, the present invention relates to an authentication technique that uses a large amount of transfer data.
2. Description of the Prior Art
In systems that transfer data such as digitized text, audio, images, and programs via a network and systems that record such data for later retrieval, it is necessary to investigate whether a user is authorized before allowing the user to access the digital data. To do so, authentication procedures are performed to verify the validity of each access performed for a network or a recording medium.
The simplest authentication technique is a technique which receives a user ID and a password from a user who wishes to access the data. This method suffers from the drawback that easy for third parties to perform unauthorized access having obtained an ID and password, such as by intercepting their communication on a transfer path, so that this technique is not especially secure.
Two examples of highly secure conventional device authentication systems are a first prior art technique which uses a one-way function and a second prior art technique which uses an encryption module and a corresponding decryption module.
FIG. 1 is a block diagram showing the construction of a device authentication system that relates to the first prior art technique which uses a one-way function. This system is composed of a verifier apparatus 10 and a claimant apparatus 20 that are connected via transfer paths 24 and 25.
In this system, the verifier apparatus 10 which verifies the claimant apparatus 20 is composed of a random number generation unit 11, a transmission unit 14 for transmitting the generated random number to the claimant apparatus 20 as authentication data, a data conversion module 12 for converting the random number using a secret one-way function f(), a reception unit 15 for receiving claimant data from the claimant apparatus 20, and a comparator unit 13 for judging whether the received claimant data matches the data generated by the data conversion module 12. It should be noted that the authentication data is challenge data that is transmitted to the verifier apparatus 10 to the claimant apparatus 20, and is data by which the verifier apparatus 10 gives the claimant apparatus 20 an opportunity to prove its validity.
On the other hand, the claimant apparatus 20 proves its validity to the verifier apparatus 10, and is composed of a reception unit 22 for receiving the authentication data sent from the verifier apparatus 10, a data conversion module 21 for converting the authentication data using a secret one-way function f(), and a transmission unit 23 for transmitting the data generated by the data conversion module 21 to the verifier apparatus 10 as the claimant data. It should be noted here that the claimant data is response data sent by the claimant apparatus 20 to the verifier apparatus 10 to prove the validity of the claimant apparatus 20.
In the present figure, the data conversion module 12 provided in the verifier apparatus 10 and the data conversion module 21 provided in the claimant apparatus 20 are the same (which is to say, both data conversion modules perform conversion using the same function f()), so that the same conversion of the random number generated by the random number generation unit 11 is performed by the verifier apparatus 10 and the claimant apparatus 20. This means that the comparison by the comparator unit 13 should result in a match. In such a case, the verifier apparatus 10 judges that the device currently in communication (the claimant apparatus 20) is equipped with a data conversion module that is the same as its own data conversion module 12, and accordingly authenticates the claimant apparatus 20.
On the other hand, when the comparator unit 13 finds that the comparison does not result in a match, the verifier apparatus 10 judges that the device currently in communication (the claimant apparatus 20) is not equipped a with a data conversion module that is the same as its own data conversion module 12, and so does not authenticate the claimant apparatus 20.
The reason a random number is generated for use as the authentication data every time authentication is to be performed by the system described above is as follows. If a third party who intercepts the communication on the transfer paths 24 and 25 obtains fixed authentication data that is used every time authentication is performed, the third party would thereafter be authenticated as a valid claimant apparatus.
FIG. 2 is a block diagram showing the construction of a device authentication system that relates to the second prior art technique which uses an encryption module and a corresponding decryption module.
While the verifier apparatus 10 and the claimant apparatus 20 in the first prior art technique are provided with the same data conversion module 12, 21, the apparatuses 30 and 40 in this second prior art technique are respectively equipped with an encryption module 32 for performing encryption according to a secret encryption algorithm E() and a decryption module 41 that performs decryption according to a secret decryption algorithm D() that is the inverse transformation of the encryption algorithm E(). In the first prior art technique, the authentication data is a random number which is transmitted as it is, with the verifier apparatus 10 comparing the results of data conversion by the data conversion modules 12 and 21. In this second prior art technique, however, the authentication data is a cryptogram that has been produced by encrypting a random number, with the verifier apparatus 30 comparing the random number with the decrypted data sent from the claimant apparatus 40.
In this second prior art technique, when the comparator unit 33 finds that the random number and the decrypted data match, the verifier apparatus 30 judges that the device currently in communication (the claimant apparatus 40) is equipped with the decryption module 41 that corresponds to its own encryption module 32, and accordingly authenticates the claimant apparatus 40.
In these conventional device authentication systems, there needs to be a large number of combinations of authentication data and claimant data. This is to prevent an unauthorized third party intercepting the communication on the transfer paths 24, 25, 44, 45 and obtaining all possible pairs of authentication data and matching claimant data, a situation which is the equivalent of the third party having decoded the algorithms f(), E(), and D(). It is also necessary to prevent an unauthorized device being used as the verifier apparatus to successively send every possible combination of authentication data to a valid claimant apparatus and, as a result, then obtain the correct claimant data for each possible authentication data.
For the prior art device authentication systems described above, it is necessary to have a number of combinations of authentication data and claimant data that is so large as to prevent the acquisition of all possible combinations of authentication data and claimant data given the effective limitations of processing performance and required time.
If the data length (bit length) of the authentication data in the above prior art device authentication systems is increased to increase the total number of combinations of authentication data and claimant data, there is the problem that the scale of the circuits used for the data conversion modules 12 and 21, the encryption module 32, and the decryption module 41 that receive an input of the authentication data will have to be greatly increased.
In the prior art device authentication system described above, the authentication data and claimant data are both 32 bits long, so that there are a total of 2.sup.32 combinations. Accordingly, 2.sup.32 combinations of authentication data and claimant data can appear on the transfer paths. If one combination appears on the transfer paths for a time period of 1 ms and is stolen by a third party, it would take the third party less than a week to obtain all of the possible combinations of authentication data and matching claimant data. Since a third party can obtain one hundredth of all of the possible combinations in little over an hour, there is a high possibility that an invalid device will soon be able to mimic a valid claimant apparatus. Accordingly, this number of combinations is not sufficient for the system to be secure.
In order to improve the security of the system, the number of combinations can be increased by increasing the bit length of the authentication data to 64 bits, although to do so, the scale of the circuits used for the data conversion modules 12 and 21, the encryption module 32, and the decryption module 41 needs to be at least doubled. The actual installation of such circuits, however, is extemely difficult due to tight restrictions regarding the scale of circuits in compact or portable electronic devices and due to the need for communication devices to perform authentication processes at high speed. As a result, such increases cannot realistically be made.